{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Maximum Path Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxPathSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树中的最大路径和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>二叉树中的<strong> 路径</strong> 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 <strong>至多出现一次</strong> 。该路径<strong> 至少包含一个 </strong>节点，且不一定经过根节点。</p>\n",
    "\n",
    "<p><strong>路径和</strong> 是路径中各节点值的总和。</p>\n",
    "\n",
    "<p>给你一个二叉树的根节点 <code>root</code> ，返回其 <strong>最大路径和</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/13/exx1.jpg\" style=\"width: 322px; height: 182px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>最优路径是 2 -&gt; 1 -&gt; 3 ，路径和为 2 + 1 + 3 = 6</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/13/exx2.jpg\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [-10,9,20,null,null,15,7]\n",
    "<strong>输出：</strong>42\n",
    "<strong>解释：</strong>最优路径是 15 -&gt; 20 -&gt; 7 ，路径和为 15 + 20 + 7 = 42\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目范围是 <code>[1, 3 * 10<sup>4</sup>]</code></li>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-maximum-path-sum](https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-maximum-path-sum](https://leetcode.cn/problems/binary-tree-maximum-path-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[-10,9,20,null,null,15,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        max_sum = float('-inf')  # node value can be negative\n",
    "        def subSum(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            nonlocal max_sum\n",
    "            left = subSum(node.left)\n",
    "            right = subSum(node.right)\n",
    "            res = node.val   # only use node itself\n",
    "            res = max(res, node.val + max(left, right))   # use itself and bigger of left and right\n",
    "            max_sum = max(max_sum, res) \n",
    "            max_sum = max(max_sum, left + right + node.val)  # use both left and right to compare with current max\n",
    "            return res\n",
    "        \n",
    "        subSum(root)\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.max = float(\"-inf\")\n",
    "        self.maxPathNode(root)\n",
    "        return self.max\n",
    "\n",
    "    def maxPathNode(self, node):\n",
    "        if not node:\n",
    "            return 0\n",
    "        leftMax = max(0, self.maxPathNode(node.left))\n",
    "        rightMax = max(0, self.maxPathNode(node.right))\n",
    "        self.max = max(self.max, leftMax + rightMax + node.val)\n",
    "        return max(0, max(leftMax, rightMax) + node.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.result = root.val\n",
    "        self.recursion(root)\n",
    "        return self.result\n",
    "\n",
    "    def recursion(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        left_max = max(0, self.recursion(root.left))\n",
    "        right_max = max(0, self.recursion(root.right))\n",
    "        path_max = root.val + left_max + right_max\n",
    "        self.result = max(path_max,self.result)\n",
    "        return root.val + max(left_max, right_max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: 'TreeNode') -> 'int':\n",
    "        a=self.m(root)\n",
    "        return max(a[0],a[1])\n",
    "    def m(self,root):\n",
    "        if root==None:\n",
    "            return 0,-999999999\n",
    "        l=self.m(root.left)\n",
    "        r=self.m(root.right)\n",
    "        return max(l[0],r[0],0)+root.val,max(l[1],r[1],l[0]+r[0]+root.val,l[0]+root.val,r[0]+root.val,root.val)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode():\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution():\n",
    "    def maxPathSum(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        ret = root.val\n",
    "        \n",
    "        def f(r):          \n",
    "            if r is None:\n",
    "                return 0\n",
    "            \n",
    "            lt = f(r.left)\n",
    "            rt = f(r.right)\n",
    "            m = max(lt, 0) + max(rt, 0) + r.val\n",
    "            \n",
    "            nonlocal ret\n",
    "            ret = max(m, ret)            \n",
    "            \n",
    "            return r.val + max(lt, rt, 0)\n",
    "        \n",
    "        f(root)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def maxsums(node):\n",
    "            if not node:\n",
    "                return [-2**31] * 2\n",
    "            left = maxsums(node.left)\n",
    "            right = maxsums(node.right)\n",
    "            return [node.val + max(left[0], right[0], 0),\n",
    "                    max(left + right + [node.val + left[0] + right[0]])]\n",
    "        return max(maxsums(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSumCore(self, root: TreeNode, sum_list):\n",
    "        if root.left is None and root.right is None:\n",
    "            sum_list.append(root.val)\n",
    "            return root.val,-65536\n",
    "        left_var = -65536\n",
    "        right_val = -65536\n",
    "        left_turn = -65536\n",
    "        right_turn = -65536\n",
    "        if root.left != None:\n",
    "            left_var,left_turn = self.maxPathSumCore(root.left, sum_list)\n",
    "        if root.right != None:\n",
    "            right_val,right_turn = self.maxPathSumCore(root.right, sum_list)\n",
    "        sum_list.append(root.val)\n",
    "        return max([root.val, left_var+root.val, right_val+root.val]),max(sum_list+[left_var+right_val+root.val,left_turn,right_turn,left_var,right_val])\n",
    "    \n",
    "    def maxPathSum(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        sum_list = []\n",
    "        return max(self.maxPathSumCore(root, sum_list))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.MaxSum = -(sys.maxsize+1)\n",
    "\n",
    "\n",
    "    def maxPathSum(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            node_Left  = dfs(node.left)\n",
    "            node_Right = dfs(node.right)\n",
    "\n",
    "            path1 = node_Left + node.val\n",
    "            path2 = node_Right + node.val\n",
    "            path3 = node_Left + node.val + node_Right\n",
    "            path4 = node.val\n",
    "\n",
    "            MaxVal = max([path1, path2, path3, path4])\n",
    "            self.MaxSum = max([MaxVal, self.MaxSum])\n",
    "\n",
    "            return max([node.val, node.val + node_Left, node.val + node_Right])\n",
    "\n",
    "        dfs(root)\n",
    "        return self.MaxSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def maxPathSum(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            #左右都为空\n",
    "            if not root.left and not root.right:\n",
    "            #不能直接返回值，因为0会被当做条件，进行判断，这样不空也会被判为空。\n",
    "            #刚开始觉得冗余，发现后面不好处理这种情况，特别是max函数返回时，也要特别处理。\n",
    "                return (root.val, root.val)\n",
    "            left = helper(root.left)\n",
    "            right = helper(root.right)\n",
    "            #左右都不为空\n",
    "            if left and right:\n",
    "                first = max(left[0] + root.val, right[0] + root.val, root.val)\n",
    "                second = max(left[1], right[1], left[0] + root.val, right[0]+ root.val, left[0] + right[0] + root.val)\n",
    "            else:\n",
    "                if not left:\n",
    "                    first = max(root.val, root.val + right[0])\n",
    "                    second = max(root.val, root.val + right[0], right[1])\n",
    "                else:\n",
    "                    first = max(root.val, root.val + left[0])\n",
    "                    second = max(root.val, root.val + left[0], left[1])\n",
    "            return (first, second)\n",
    "        res = helper(root)\n",
    "        return max(res[0], res[1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        scores = {}\n",
    "        res = root.val\n",
    "        self.calculate(root, scores)\n",
    "        arr = [root]\n",
    "        while len(arr) > 0:\n",
    "            cur = arr.pop(0)\n",
    "            if cur.left != None:\n",
    "                arr.append(cur.left)\n",
    "            if cur.right != None:\n",
    "                arr.append(cur.right)\n",
    "            cur_res = cur.val\n",
    "            if cur.left in scores and scores[cur.left] > 0:\n",
    "                cur_res += scores[cur.left]\n",
    "            if cur.right in scores and scores[cur.right] > 0:\n",
    "                cur_res += scores[cur.right]\n",
    "            res = max(res, cur_res)\n",
    "        \n",
    "        return res\n",
    "        \n",
    "        \n",
    "    def calculate(self, root, scores):\n",
    "        if root.left == None and root.right == None:\n",
    "            scores[root] = root.val\n",
    "            return \n",
    "        res = root.val\n",
    "        if root.left != None:\n",
    "            self.calculate(root.left, scores)\n",
    "            if root.val + scores[root.left] > res:\n",
    "                res = root.val + scores[root.left]\n",
    "        if root.right != None:\n",
    "            self.calculate(root.right, scores)\n",
    "            if root.val + scores[root.right] > res:\n",
    "                res = root.val + scores[root.right]\n",
    "        scores[root] = res\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: 'TreeNode') -> 'int':\n",
    "        max_uni = {None: 0}\n",
    "        max_duo = {None: float('-inf')}\n",
    "        \n",
    "        stack, last = [], None\n",
    "        if root:\n",
    "            stack.append(root)\n",
    "            node = root.left\n",
    "        while stack:\n",
    "            if node:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = stack[-1]\n",
    "                if node.right and last != node.right:\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    node = stack.pop()\n",
    "                    \n",
    "                    max_uni[node] = node.val + max(0, max(max_uni[node.left], max_uni[node.right]))\n",
    "                    max_duo[node] = max(max_duo[node.left], max_duo[node.right])\n",
    "                    max_duo[node] = max(max_duo[node], node.val + max(0, max_uni[node.left]) + max(0, max_uni[node.right]))\n",
    "                    \n",
    "                    last = node\n",
    "                    node = None\n",
    "        \n",
    "        return max_duo[root]\n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        node = root\n",
    "        stack = []\n",
    "        while node:\n",
    "            stack.append([node, True, False]) #x[1]: 左边已“压缩”；x[2]：右边已“压缩”\n",
    "            node = node.left\n",
    "        res = stack[-1][0].val\n",
    "\n",
    "        while len(stack) != 0:\n",
    "            node = stack[-1][0]\n",
    "            if not node.left and not node.right:\n",
    "                res = max(res, node.val)\n",
    "                stack.pop()\n",
    "            elif stack[-1][1] and stack[-1][2]:\n",
    "                left_val = max(node.left.val, 0) if node.left else 0\n",
    "                right_val = max(node.right.val, 0) if node.right else 0\n",
    "                temp_max = node.val + left_val + right_val\n",
    "                temp_sum = node.val + max(left_val, right_val)\n",
    "                if temp_sum <= 0:\n",
    "                    node.left, node.right, node.val = None, None, 0\n",
    "                else:\n",
    "                    node.left, node.right, node.val = None, None, temp_sum\n",
    "                    res = max(res, temp_max)\n",
    "                stack.pop()\n",
    "            elif not stack[-1][1]:\n",
    "                stack[-1][1] = True\n",
    "                if node.left: stack.append([node.left, False, False])\n",
    "                continue\n",
    "            else:\n",
    "                stack[-1][2] = True\n",
    "                if node.right: stack.append([node.right, False, False])\n",
    "                continue\n",
    "\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        st1=[]\n",
    "        st2=[]\n",
    "        \n",
    "\n",
    "        \n",
    "        while(root or st1):\n",
    "            while(root):\n",
    "                 \n",
    "                st1.append(root)\n",
    "                st2.append(root)\n",
    "                root=root.right\n",
    "            if not st1:\n",
    "                break\n",
    "            root=st1.pop()\n",
    "            root=root.left\n",
    "            \n",
    "        \n",
    "        st2=st2[::-1]\n",
    "        \n",
    "        if st2:\n",
    "            max_val=st2[0].val\n",
    "        else:\n",
    "            return 0\n",
    "        \n",
    "        # for i in st2:\n",
    "        #     max_val=max(max_val,i.val)\n",
    "            \n",
    "        for i in st2:\n",
    "            leftt=i.left.val if(i.left) else 0\n",
    "            rightt=i.right.val if(i.right) else 0\n",
    "            max_val=max(max_val,i.val,i.val,i.val+leftt,i.val+rightt,i.val+leftt+rightt)\n",
    "            i.val=max(i.val,i.val+leftt,i.val+rightt)\n",
    "            \n",
    "            # if(i.left):\n",
    "            #     i.val=max(i.val,i.left.val+i.val)\n",
    "            # if(i.right):\n",
    "            #     i.val=max(i.val,i.right.val+i.val)\n",
    "            # max_val=max(max_val,i.val)\n",
    "        return max_val\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        stack = [root]\n",
    "        result = []\n",
    "        while stack:\n",
    "            root = stack.pop()\n",
    "            result.append(root)\n",
    "            if root.left:\n",
    "                stack.append(root.left)\n",
    "            if root.right:\n",
    "                stack.append(root.right)\n",
    "        re= result[-1].val\n",
    "        for i in result[::-1]:\n",
    "            if i.left:\n",
    "                a = max([i.left.val, 0])\n",
    "            else:\n",
    "                a = 0\n",
    "            if i.right:\n",
    "                b = max([i.right.val, 0])\n",
    "            else:\n",
    "                b = 0\n",
    "            re = max([re, a+b+i.val])\n",
    "            i.val += max([a, b])\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        st = []\n",
    "        lastprocessed = None\n",
    "        ret = -float(\"inf\")\n",
    "        retstack = []\n",
    "        while root or st:\n",
    "            while root:\n",
    "                st.append(root)\n",
    "                root = root.left\n",
    "            root = st[-1]\n",
    "            if not root.right or root.right == lastprocessed:\n",
    "                # process root\n",
    "                right = 0\n",
    "                if root.right:\n",
    "                    right = retstack.pop()\n",
    "                left = 0\n",
    "                if root.left:\n",
    "                    left = retstack.pop()\n",
    "                ret = max(ret, root.val + max(right, 0) + max(left, 0))\n",
    "                retstack.append(root.val + max(left, right, 0))\n",
    "                lastprocessed = root\n",
    "                st.pop()\n",
    "                root = None\n",
    "            else:\n",
    "                root = root.right\n",
    "        return ret\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        result = float('-inf')\n",
    "        all_stacks = []\n",
    "        cur_stack = [root]\n",
    "        while cur_stack:\n",
    "            tmp_stack = []\n",
    "            for node in cur_stack:\n",
    "                if node.left:\n",
    "                    tmp_stack.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp_stack.append(node.right)\n",
    "            all_stacks.append(cur_stack)\n",
    "            cur_stack = tmp_stack\n",
    "        \n",
    "        for i in range(len(all_stacks)-1, -1, -1):\n",
    "            for node in all_stacks[i]:\n",
    "                left_val = node.left.max_value if node.left else 0\n",
    "                right_val = node.right.max_value if node.right else 0\n",
    "                node.max_value = max(left_val + node.val, right_val + node.val, node.val)\n",
    "                result = max(result, node.max_value, left_val + node.val + right_val)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        ans=[]\n",
    "        def isleaf(root):\n",
    "            if root.left==None and root.right==None:\n",
    "                return True\n",
    "            return False\n",
    "        def istoleaf(root):\n",
    "            if root.left and root.right:\n",
    "                if isleaf(root.left) and isleaf(root.right):\n",
    "                    max1=max(root.left.val,root.right.val,root.left.val+root.right.val+root.val)\n",
    "                    max2=max(root.left.val+root.val,root.right.val+root.val,root.val)\n",
    "                    ans.append(max1)  \n",
    "                    return max2\n",
    "            elif root.left:\n",
    "                if isleaf(root.left):\n",
    "                    max1=root.left.val\n",
    "                    max2=max(root.val,root.left.val+root.val)\n",
    "                    ans.append(max1)\n",
    "                    return max2\n",
    "            elif root.right:\n",
    "                if isleaf(root.right):\n",
    "                    max1=root.right.val\n",
    "                    max2=max(root.val,root.right.val+root.val)\n",
    "                    ans.append(max1)\n",
    "                    return max2\n",
    "            else:\n",
    "                ans.append(root.val)\n",
    "                return root.val\n",
    "            return None\n",
    "        stack=[root]\n",
    "        while stack:\n",
    "            root=stack.pop()\n",
    "            an=istoleaf(root)\n",
    "            #print(an)\n",
    "            if an==None:  \n",
    "                stack.append(root)  \n",
    "                if root.left and istoleaf(root.left)==None:\n",
    "                    stack.append(root.left)\n",
    "                elif root.left:\n",
    "                    root.left=TreeNode(istoleaf(root.left))\n",
    "                if root.right and istoleaf(root.right)==None:\n",
    "                    stack.append(root.right) \n",
    "                elif root.right:\n",
    "                    root.right=TreeNode(istoleaf(root.right))\n",
    "                #print(root.right)\n",
    "            elif type(an)==int:\n",
    "                ans.append(an)\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        stack = [root]\n",
    "        res = []\n",
    "        max_sum = - 2**10\n",
    "        while stack :\n",
    "            node = stack.pop()\n",
    "            res.append(node)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "        while res:\n",
    "            node = res.pop()\n",
    "            l = node.left.val if node.left else 0\n",
    "            r = node.right.val if node.right else 0\n",
    "            node.val += max(l , r , 0)\n",
    "            max_sum = max(max_sum , node.val + max(min(l , r) , 0))     \n",
    "        \n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def max_path_cross(node):\n",
    "    max_value=node.val;\n",
    "    if node.left==None:\n",
    "        max_left=0;\n",
    "    else:\n",
    "        max_left=max(0,node.left.val);\n",
    "    if node.right==None:\n",
    "        max_right=0;\n",
    "    else:\n",
    "        max_right=max(0,node.right.val);    \n",
    "    node.val=max(max_value+max_left,max_value+max_right);\n",
    "    return max_value+max_left+max_right;\n",
    "# def max_sub_line(node):\n",
    "#     if node==None:\n",
    "#         return 0;\n",
    "#     else:\n",
    "#         return max(0,max_sub_line(node.left)+node.val,max_sub_line(node.right)+node.val)\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        #*******************************************************************************\n",
    "        #A path has a fixed structed with a root. So I plan to start with any \n",
    "        #node, and expand the node to the left or right.\n",
    "        #Time complexity: n nodes, each node at most travel 2*2^(lg(n))  So n^2 in total\n",
    "        #*******************************************************************************\n",
    "        #Step1: Get all the nodes\n",
    "        Node_stack=[];\n",
    "        cur_level_nodes=[root];\n",
    "        while cur_level_nodes!=[]:\n",
    "            next_level_nodes=[];\n",
    "            while cur_level_nodes!=[]:\n",
    "                node=cur_level_nodes.pop();\n",
    "                Node_stack.append(node);\n",
    "                if node.left!=None:\n",
    "                    next_level_nodes.append(node.left);\n",
    "                if node.right!=None:\n",
    "                    next_level_nodes.append(node.right);\n",
    "            cur_level_nodes=next_level_nodes[0:];\n",
    "        max_path=-10000000;\n",
    "        while Node_stack!=[]:\n",
    "            node=Node_stack.pop();\n",
    "            max_path=max(max_path,max_path_cross(node))\n",
    "        return max_path\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        max_sum = -9999999\n",
    "        stack = []\n",
    "        stack.append(root)\n",
    "        reverse_stack = []\n",
    "        while len(stack) > 0:\n",
    "            top = stack.pop()\n",
    "            max_sum = max(max_sum, top.val)\n",
    "            reverse_stack.append(top)\n",
    "            if top.left is not None:\n",
    "                stack.append(top.left)\n",
    "            if top.right is not None:\n",
    "                stack.append(top.right)\n",
    "        while len(reverse_stack) > 0:\n",
    "            top = reverse_stack.pop()\n",
    "            lval = 0 if top.left is None else top.left.val\n",
    "            rval = 0 if top.right is None else top.right.val\n",
    "            oval = top.val\n",
    "            top.val = max(0, top.val, top.val + lval, top.val + rval)\n",
    "            max_sum = max(max_sum, oval, oval + lval, oval + rval, oval + lval + rval)\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.v1 = None\n",
    "        self.v2 = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        if self.isleaf(root):\n",
    "            return root.val\n",
    "        tline = [root]\n",
    "        outputline = []\n",
    "        while len(tline) > 0:\n",
    "            node = tline.pop()\n",
    "            if node.left:\n",
    "                tline.append(node.left)\n",
    "            if node.right:\n",
    "                tline.append(node.right)\n",
    "\n",
    "            outputline.append(node)\n",
    "\n",
    "        maxpath = None\n",
    "        while len(outputline) > 0:\n",
    "            node = outputline.pop()\n",
    "            if self.isleaf(node):\n",
    "                node.v1 = max(node.val, 0)\n",
    "                # node.v2 = node.val\n",
    "                if maxpath is None:\n",
    "                    maxpath = node.val\n",
    "                elif node.val > maxpath:\n",
    "                    maxpath = node.val\n",
    "\n",
    "            else:\n",
    "                # v0\n",
    "                if node.val > maxpath:\n",
    "                    maxpath = node.val\n",
    "\n",
    "                l1 = 0\n",
    "                if node.left:\n",
    "                    l1 = node.left.v1\n",
    "\n",
    "                r1 = 0\n",
    "                if node.right:\n",
    "                    r1 = node.right.v1\n",
    "\n",
    "                # v1\n",
    "                node.v1 = max(l1 + node.val, r1 + node.val, node.val)\n",
    "                if node.v1 > maxpath:\n",
    "                    maxpath = node.v1\n",
    "                node.v1 = max(node.v1,0)\n",
    "\n",
    "                # v2\n",
    "                node.v2 = l1 + r1 + node.val\n",
    "                if node.v2 > maxpath:\n",
    "                    maxpath = node.v2\n",
    "\n",
    "        return maxpath\n",
    "\n",
    "    def isleaf(self, node: Optional[TreeNode]) -> bool:\n",
    "        if node.left is None and node.right is None:\n",
    "            return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        # cur.val为以cur为根节点的子树，以cur为终点的最大路径和\n",
    "        st = [root]\n",
    "        ans = -1001\n",
    "        while st:\n",
    "            cur = st.pop()\n",
    "            if cur:\n",
    "                st.append(cur)\n",
    "                st.append(None)\n",
    "                if cur.right:\n",
    "                    st.append(cur.right)\n",
    "                if cur.left:\n",
    "                    st.append(cur.left)\n",
    "            else:\n",
    "                cur = st.pop()\n",
    "                temp0, temp1 = 0, 0\n",
    "                if cur.left:\n",
    "                    temp0 = max(cur.left.val, temp0)\n",
    "                    temp1 += max(cur.left.val, 0)\n",
    "                if cur.right:\n",
    "                    temp0 = max(cur.right.val, temp0)\n",
    "                    temp1 += max(cur.right.val, 0)\n",
    "                ans = max(ans, cur.val + temp0, cur.val + temp1)\n",
    "                cur.val += temp0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    max_sum=-inf\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        self.max_sum=root.val\n",
    "        stack1=[]\n",
    "        stack2=[]\n",
    "        stack1.append(root)\n",
    "        while stack1:\n",
    "            root=stack1.pop()\n",
    "            if root.left:\n",
    "                stack1.append(root.left)\n",
    "            if root.right:\n",
    "                stack1.append(root.right)\n",
    "            stack2.append(root)\n",
    "        while stack2:\n",
    "            root=stack2.pop()\n",
    "            max_sum=root.val\n",
    "            if not root.left: \n",
    "                left_val=-inf\n",
    "            else: \n",
    "                left_val=root.left.val\n",
    "            if not root.right: \n",
    "                right_val=-inf\n",
    "            else: \n",
    "                right_val=root.right.val\n",
    "            left_root=left_val+root.val\n",
    "            right_root=right_val+root.val\n",
    "            left_right_root=right_val+left_val+root.val\n",
    "            max_sum = max(max_sum,left_right_root,left_root,right_root)\n",
    "            self.max_sum = max(self.max_sum,max_sum)\n",
    "            root.val = max(left_root,right_root,root.val)\n",
    "        return self.max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\r\n",
    "        \r\n",
    "        stack1 = []\r\n",
    "        stack2 = []\r\n",
    "        max_son_val = -inf\r\n",
    "        stack1.append(root)\r\n",
    "        while len(stack1) > 0 :\r\n",
    "            node = stack1.pop()\r\n",
    "            if node.right != None :\r\n",
    "                stack1.append(node.right)\r\n",
    "            if node.left != None :\r\n",
    "                stack1.append(node.left)\r\n",
    "            stack2.append(node)\r\n",
    "        while len(stack2) > 0 :\r\n",
    "            node = stack2.pop()\r\n",
    "            if node.left != None and node.right != None :\r\n",
    "                max_son_val = max(max_son_val,node.val + node.left.val + node.right.val)\r\n",
    "                node.val += max(node.left.val , node.right.val) \r\n",
    "            elif node.left == None and node.right != None :\r\n",
    "                max_son_val = max(max_son_val,node.val + node.right.val)\r\n",
    "                node.val += node.right.val\r\n",
    "            elif node.left != None and node.right == None :\r\n",
    "                max_son_val = max(max_son_val,node.val + node.left.val)\r\n",
    "                node.val += node.left.val\r\n",
    "            else :\r\n",
    "                max_son_val = max(max_son_val,node.val )\r\n",
    "            if node.val < 0 :\r\n",
    "                node.val = 0\r\n",
    "        return max_son_val\r\n",
    "        \r\n",
    "\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        node_stack=[]\n",
    "        max_double_path=root.val\n",
    "        cur_node=root\n",
    "        cur_node.lvisited=False\n",
    "        break_flag=False\n",
    "        while True:\n",
    "            while cur_node.left:\n",
    "                node_stack.append(cur_node)\n",
    "                cur_node=cur_node.left\n",
    "                cur_node.lvisited=False\n",
    "            while not cur_node.right or cur_node.lvisited:\n",
    "                if cur_node.left:\n",
    "                    left_path=max(0,cur_node.left.max_path)\n",
    "                else:\n",
    "                    left_path=0\n",
    "                if cur_node.right:\n",
    "                    right_path=max(0,cur_node.right.max_path)\n",
    "                else:\n",
    "                    right_path=0\n",
    "                cur_node.max_path=max(left_path,right_path)+cur_node.val\n",
    "                cur_double_path=left_path+cur_node.val+right_path\n",
    "                if cur_double_path>max_double_path:\n",
    "                    max_double_path=cur_double_path\n",
    "                if node_stack:\n",
    "                    cur_node=node_stack.pop()\n",
    "                else:\n",
    "                    break_flag=True\n",
    "                    break\n",
    "            if break_flag:\n",
    "                break\n",
    "            if cur_node.right and not cur_node.lvisited:\n",
    "                node_stack.append(cur_node)\n",
    "                cur_node.lvisited=True\n",
    "                cur_node=cur_node.right\n",
    "                cur_node.lvisited=False\n",
    "\n",
    "        return max_double_path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = float(\"-inf\")\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        self.getMax(root)\n",
    "        return self.result\n",
    "\n",
    "    def getMax(self, root):\n",
    "        if root == None:\n",
    "            return 0\n",
    "        \n",
    "        left = max(0,self.getMax(root.left))\n",
    "        right = max(0,self.getMax(root.right))\n",
    "\n",
    "        self.result=max(self.result,left+right+root.val)\n",
    "\n",
    "        return max(left,right)+root.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        max_sum = float('-inf')\n",
    "        stack = [(root, False, False)]\n",
    "\n",
    "        while stack:\n",
    "            node, left_visited, right_visited = stack.pop()\n",
    "\n",
    "            if not left_visited:\n",
    "                stack.append((node, True, right_visited))\n",
    "                if node.left:\n",
    "                    stack.append((node.left, False, False))\n",
    "            elif not right_visited:\n",
    "                stack.append((node, True, True))\n",
    "                if node.right:\n",
    "                    stack.append((node.right, False, False))\n",
    "            else:\n",
    "                left = node.left.val if node.left else 0\n",
    "                right = node.right.val if node.right else 0\n",
    "\n",
    "                max_sum = max(max_sum, node.val, node.val + left, node.val + right, node.val + left + right)\n",
    "                node.val = max(node.val, node.val + max(left, right))\n",
    "\n",
    "        return max_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        def getMax(index):\n",
    "            path = [index]\n",
    "            index.val += 3000\n",
    "            ans = -2000\n",
    "            cnt = 0\n",
    "            while(path):\n",
    "                if path[-1].left and path[-1].left.val <= 1000:\n",
    "                    path.append(path[-1].left)\n",
    "                    path[-1].val += 3000\n",
    "                elif path[-1].right and path[-1].right.val <= 1000:\n",
    "                    path.append(path[-1].right)\n",
    "                    path[-1].val += 3000\n",
    "                else:\n",
    "                    tmp = path[-1].val - 3000\n",
    "                    tmp = tmp + max(path[-1].left.val - 3000, 0) if path[-1].left else tmp\n",
    "                    tmp = tmp + max(path[-1].right.val - 3000, 0) if path[-1].right else tmp\n",
    "                    ans = max(ans, tmp)\n",
    "                    \n",
    "\n",
    "                    if path[-1].left and path[-1].right:\n",
    "                        path[-1].val += max(max(path[-1].left.val, path[-1].right.val) - 3000, 0)\n",
    "                    elif path[-1].left:\n",
    "                        path[-1].val += max(path[-1].left.val  -3000, 0)\n",
    "                    elif path[-1].right:\n",
    "                        path[-1].val += max(path[-1].right.val -3000, 0) \n",
    "                    # print(path[-1].val -3000) \n",
    "                    path.pop()\n",
    "                    \n",
    "            return ans\n",
    "        \n",
    "        return getMax(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        maxpathsum = root.val\n",
    "        stack = []\n",
    "        root.as_path = root.val\n",
    "        root.as_topNode = root.val\n",
    "        stack.append(root)\n",
    "        pnt = 0\n",
    "        while pnt < len(stack):\n",
    "            if stack[pnt].left:\n",
    "                stack[pnt].left.as_path = stack[pnt].left.val\n",
    "                stack[pnt].left.as_topNode = stack[pnt].left.val\n",
    "                stack.append(stack[pnt].left)\n",
    "            if stack[pnt].right:\n",
    "                stack[pnt].right.as_path = stack[pnt].right.val\n",
    "                stack[pnt].right.as_topNode = stack[pnt].right.val\n",
    "                stack.append(stack[pnt].right)\n",
    "            pnt += 1\n",
    "        while stack:\n",
    "            top = stack.pop()\n",
    "            left_path = 0 if ((not top.left) or (top.left.as_path < 0)) else top.left.as_path\n",
    "            right_path =  0 if ((not top.right) or (top.right.as_path < 0)) else top.right.as_path\n",
    "            top.as_path += max(left_path,right_path)\n",
    "            top.as_topNode += left_path + right_path\n",
    "            maxpathsum = max(maxpathsum,max(top.as_path,top.as_topNode))\n",
    "        return maxpathsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans=float('-inf')\n",
    "        def dfs(node):\n",
    "            if not node:return 0\n",
    "            left=max(dfs(node.left),0)\n",
    "            right=max(dfs(node.right),0)\n",
    "            maxpath=node.val+left+right\n",
    "            self.ans=max(self.ans,maxpath)\n",
    "            return node.val+max(left,right)\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        def helper(node):\n",
    "            nonlocal max_sum\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            # 计算左右孩子的最大贡献值\n",
    "            # 只有在贡献值大于 0 时，才会选取对应子节点\n",
    "            left_gain = max(helper(node.left), 0)\n",
    "            right_gain = max(helper(node.right), 0)\n",
    "\n",
    "            # 节点的最大路径和取决于该节点的值、该节点的左右孩子的贡献值\n",
    "            price_newpath = node.val + left_gain + right_gain\n",
    "\n",
    "            # 更新答案\n",
    "            max_sum = max(max_sum, price_newpath)\n",
    "\n",
    "            # 返回节点的最大贡献值\n",
    "            return node.val + max(left_gain, right_gain)\n",
    "        \n",
    "        max_sum = float('-inf')\n",
    "        helper(root)\n",
    "        return max_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        res = float('-inf')\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if root is None:\n",
    "                return 0\n",
    "            leftmax = dfs(root.left)\n",
    "            rightmax = dfs(root.right)\n",
    "            res = max(res, max(leftmax, 0) + max(rightmax, 0) + root.val)\n",
    "            return max(leftmax, rightmax, 0) + root.val\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        maxSum = float(\"-inf\")\n",
    "        def maxGain(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            leftGain = max(maxGain(node.left), 0)\n",
    "            rightGain = max(maxGain(node.right), 0)\n",
    "            \n",
    "            nonlocal maxSum\n",
    "            maxSum = max(maxSum, leftGain + node.val + rightGain)\n",
    "            \n",
    "            return max(leftGain, rightGain) + node.val\n",
    "        maxGain(root)\n",
    "        return maxSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        max_val = -float('inf')\n",
    "        max_node_val = -float('inf')\n",
    "\n",
    "        def maxRootSum(root: Optional[TreeNode]) -> int:    \n",
    "            nonlocal max_val\n",
    "            nonlocal max_node_val\n",
    "\n",
    "            if not root:\n",
    "                return 0\n",
    "\n",
    "            # root.val\n",
    "            # if root.left:\n",
    "            #     maxRootSum(root.left)\n",
    "            # if root.right:\n",
    "            #     maxRootSum(root.right)\n",
    "\n",
    "            max_node_val = max(max_node_val, root.val)\n",
    "\n",
    "            # if root.left and root.right:\n",
    "            #     root_left = max(0, maxRootSum(root.left))\n",
    "            #     root_right = max(0, maxRootSum(root.right))\n",
    "            #     max_val = max(max_val, root.val + root_left + root_right)\n",
    "            #     # print(root.left.val, root.right.val, root_left, root_right, max_val)\n",
    "            #     return max(root_left, root_right) + root.val\n",
    "            # elif root.left:\n",
    "            #     root_left = max(0, maxRootSum(root.left))\n",
    "            #     max_val = max(max_val, root.val + root_left)\n",
    "            #     return root_left + root.val             \n",
    "            # elif root.right:\n",
    "            #     root_right = max(0, maxRootSum(root.right))\n",
    "            #     max_val = max(max_val, root.val + root_right)\n",
    "            #     return root_right + root.val   \n",
    "            # else:\n",
    "            #     max_val = max(max_val, root.val)\n",
    "            #     return root.val\n",
    "\n",
    "            root_left = max(0, maxRootSum(root.left))\n",
    "            root_right = max(0, maxRootSum(root.right))\n",
    "            max_val = max(max_val, root.val + root_left + root_right)\n",
    "            return max(root_left, root_right) + root.val\n",
    "                    \n",
    "        max_val = max(maxRootSum(root), max_val)\n",
    "        \n",
    "        # if max_node_val < 0:\n",
    "        #     max_val = max_node_val\n",
    "        return max_val\n",
    "    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
